#include<bits/stdc++.h> 
using namespace std;
//  与乙级1025一模一样

int main(){
	int start, n, k;
	cin>>start>>n>>k;
	map<int, int> chain_dic;
	map<int, int> data_dic;
	for(int i = 0;i<n;i++){
		int add, data, nex;
		cin>>add>>data>>nex;
		data_dic[add] = data;
		chain_dic[add] = nex;
	}
	vector<int> chain;
	chain.push_back(start);
	while(true){
		int now = chain.back();
		if(chain_dic[now] == -1) break;
		else chain.push_back(chain_dic[now]); 
	}
	vector<int> temp;
	vector<int> result;
	int count = 1;
	vector<int>::iterator it;
	for(it=chain.begin();it!=chain.end();it++){
		if(count==k){
			temp.push_back(*(it));
			for(int i = temp.size()-1;i>=0;i--){
				result.push_back(temp[i]);
			}
			count = 1;
			temp = vector<int>();
		}
		else{
			temp.push_back(*(it));
			count += 1;
		}
	}
	if(count != 1){
		for(int i = chain.size()-count+1;i<chain.size();i++) result.push_back(chain[i]);
	}
	for(int i = 0;i<result.size()-1;i++) chain_dic[result[i]] = result[i+1];
	chain_dic[result[result.size()-1]] = -1;
	for(int i = 0;i<result.size();i++){
		if(chain_dic[result[i]]==-1) printf("%000005d %d -1", result[i], data_dic[result[i]]);
		else printf("%000005d %d %000005d\n", result[i], data_dic[result[i]], chain_dic[result[i]]);
	}
	return 0;
}